package middle;
/**
 * 11. 盛最多水的容器
 * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 *
 * 说明：你不能倾斜容器，且 n 的值至少为 2。
 *
 * 示例：
 *
 * 输入：[1,8,6,2,5,4,8,3,7]
 * 输出：49
 * 解释：第二个元素到最后一个元素是8 和 7 取最小值7 然后两个元素坐标相差7 所以容量是7*7 = 49
 *
 * */
public class MaxArea {
    // 暴力解法 时间复杂度： O(n^2) 空间复杂度： O(1)
    public int maxArea(int[] height){
        int max = 0;
        for (int i = 0; i <height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                max = Math.max(max, Math.min(height[i], height[j]) * (j - i));
            }
        }
        return max;
    }

    /**
     * 双指针法 空间复杂度: O(n) 时间复杂度 O(1)
     * 思路：
     * 用两个指针指向数组的两端，固定高的一端，移动低的一端，求出最大值
     *
     * */
    public int maxArea1(int[] height){
        int i = 0, j = height.length - 1;
        int max = 0;
        while(i < j){
            max = Math.max(max, Math.min(height[i], height[j]) * (j-i));
            if(height[i] >= height[j]){
                j--;
            }else{
                i++;
            }
        }
        return max;
    }



    // main
    public static void main(String[] args) {
        MaxArea m = new MaxArea();
        int i = m.maxArea1(new int[]{1,8,6,2,5,4,8,3,7});
        System.out.print(i);
    }
}
